/*
https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
力扣673.最长递增子序列
*/
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);
        vector<int> count(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {  
                if (nums[j] < nums[i]) { 
                    if(dp[j]+1>dp[i]) 
                    {
                        dp[i]=dp[j]+1;
                        count[i]=count[j];
                    }
                    else if(dp[j]+1==dp[i]){
                    count[i]+=count[j];
                    }
                }
            }
        }
        int res=0,maxnum=0;
        for(int i=0;i<n;++i) 
            maxnum=max(maxnum,dp[i]);
            for(int i=0;i<n;++i){
                if(dp[i]==maxnum) res+=count[i];
            }
        return res;
    }
};